This invention relates to a method and apparatus for transmitting digital data words in an error-correction format and, more particularly, to a method and apparatus whereby the error-correction ability of the transmitted information is improved.
Various error-correction encoding techniques have been proposed for use in transmitting and/or recording digital data. For example, digital data in the form of data words, such as pulse code modulated (PCM) signals, when transmitted or recorded, may be subjected to errors known as random and burst errors. A random error distorts or destroys isolated bits of the PCM signal. A burst error distorts or destroys one or more data words included in the PCM signal. Although relatively simple error-correction techniques, such as the use of parity words to accompany the PCM signal, are known to be useful in correcting random errors, more sophisticated error-correction encoding techniques are needed in order to correct burst errors.
In one technique which has been proposed, data words, such as PCM words, are encoded in a so-called time-interleaved format. That is, successive PCM words X.sub.0, X.sub.1, X.sub.2, . . . X.sub.k-1 are distributed to respective ones of k channels. These PCM words X.sub.0 . . . X.sub.k-1 thus appear as parallel words. Each word, or each channel, is subjected to a time delay of a respectively different amount. For example, PCM word X.sub.0 is delayed by a delay time D.sub.0, PCM word X.sub.1 is delayed by a delay time of D.sub.1, and so on, with PCM word X.sub.k-1 delayed by the time delay D.sub.k-1. These time delays result in a time-interleaving effect, with delayed PCM word X.sub.0 being represented as Y.sub.0, delayed PCM word X.sub.1 being represented as Y.sub.1, and so on, with delayed word X.sub.k-1 being represented as Y.sub.k-1. That is, delayed PCM words Y.sub.0 . . . Y.sub.k-1 exhibit a time-interleaved relationship. A parity word P.sub.x is produced in response to the original, undelayed PCM words X.sub.0 . . . X.sub.k-1. As one example thereof, the parity word P.sub.x is produced by supplying, on a bit-by-bit basis, all of the PCM words X.sub.0 . . . X.sub.k-1 to a modulo-2 adder. The output of this adder is the parity word P.sub.x having the same number of bits as the bits which constitute each PCM word. Another parity word R.sub.y is produced in response to the time-interleaved PCM words Y.sub.0 . . . Y.sub.k-1. That is, these time-interleaved PCM words are supplied to yet another modulo-2 adder, the output of which is the parity word R.sub.y. The first-mentioned parity word P.sub.x is delayed by a suitable time delay D.sub.k, resulting in a delayed parity word P.sub.y. Now, the time-interleaved PCM words Y.sub.0 . . . Y.sub.k-1, together with the delayed parity word P.sub.y and the second-mentioned parity word R.sub.y are transmitted as a transmission block. This transmission block may be transmitted in parallel-by-word form or, preferably, in seriatum. A synchronizing signal SYNC is inserted into this transmission block as the first word thereof; and then this transmission block may be transmitted or recorded on a suitable record medium.
When the time-interleaved encoded information of the foregoing type is reproduced, the transmission block, formed of PCM words Y.sub.0 . . . Y.sub.k-1, and the parity words P.sub.y and R.sub.y are recovered and are supplied in separate channels, as by a suitable distributing device, such as a demultiplexer. If an error is present in any one of the recovered PCM words Y.sub.0 . . . Y.sub.k-1, this error can be corrected in accordance with the parity word R.sub.y, as is known to those of ordinary skill in the art. That is, conventional parity-error-correction techniques can be used to correct an error which may be present in one of these PCM words. Then, once the erroneous PCM word is corrected, the PCM words Y.sub.0 . . . Y.sub.k-1 are time-deinterleaved. The parity word P.sub.y is delayed by an amount sufficient to cancel the original time delay which was imparted during the encoding process; thereby recovering the parity word P.sub.x. The time-deinterleaving process is obtained by delaying each of the recovered PCM words Y.sub.0 . . . Y.sub.k-1 by an amount sufficient to cancel the original delays D.sub.0, D.sub.1, . . . D.sub.k-1 which had been used in the time-interleaving encoding process. Thus, the original PCM words X.sub.0 . . . X.sub.k-1, exhibiting the original time relationship, is obtained. Any error which may be present in one of these PCM words is corrected in accordance with conventional parity-error-correction techniques by using the recovered parity word P.sub.x.
While the foregoing time-interleaving encoding technique generally operates in a satisfactory manner, that is, it is capable of correcting burst errors which may be present in the reproduced time-interleaved PCM words Y.sub.0 . . . Y.sub.k-1 due to the inherent dispersal of such errors in different time-deinterleaved blocks, error correction is inhibited if the parity word R.sub.y or the parity word P.sub.y is erroneous. This difficulty is overcome by another technique described generally in U.S. application Ser. No. 31,030, filed Apr. 18, 1979. As described in this application, the delayed parity word P.sub.y, which is derived from the original PCM words X.sub.0 . . . X.sub.k-1, is supplied to the modulo-2 adder as the time-interleaved PCM words Y.sub.0 . . . Y.sub.k-1. Hence, the second-mentioned parity word R.sub.y is derived as a function of the time-interleaved PCM words and also the delayed parity word P.sub.y. Consequently, if, during reproduction, the reproduced parity word P.sub.y is erroneous, this error can be corrected by using the parity word R.sub.y in accordance with conventional parity-error-correction techniques. This means that, once the parity word P.sub.y is corrected, the time-deinterleaved PCM words X.sub.0 . . . X.sub.k-1, recovered from the reproduced time-interleaved PCM words, may be error-corrected.
However, in the time-interleaved error correction coding technique described in the aforementioned application, if the parity word P.sub.y and also a PCM word in a recovered time-interleaved block both are erroneous, the parity word P.sub.y cannot be corrected. Furthermore, if two words in two successive recovered time-interleaved blocks are erroneous, the recovered time-deinterleaved words cannot be corrected. The possibility of the occurrence of such errors to prevent error correction is reduced in accordance with the technique disclosed in copending application Ser. No. 123,721, filed Feb. 22, 1980. In this latter application, the parity word R.sub.y is delayed and fed back to the first-mentioned modulo-2 adder, such that the parity word P.sub.x is derived from the PCM words X.sub.0 . . . X.sub.k-1, together with the delayed parity word R.sub.y. As a result of this arrangement, many errors which may occur in the reproduced parity word R.sub.y now may be corrected by using parity word P.sub.x and conventional parity-error-correction techniques. Consequently, the error correcting ability of this encoding arrangement is markedly improved.
Nevertheless, one disadvantage which is common to all of the foregoing time-interleaved error correction techniques is the ability to correct only a single erroneous word (be it a PCM word or a parity word) included in any given block. That is, only one erroneous word in the recovered time-interleaved block may be corrected and, similarly, only one erroneous word in the time-deinterleaved block may be corrected. A burst error having a substantial duration so as to exceed the inherent dispersal thereof due to the time-interleaving arrangement will, therefore, distort two or more words which are present in the same time-deinterleaved block. To improve the dispersal effect of such prolonged burst errors, it has been found advantageous to impart additional delays to the PCM words Y.sub.0 . . . Y.sub.k-1, as well as to the parity words P.sub.y and R.sub.y. This results in a further interleaved effect. Also, an error detecting code, such as the cyclic redundancy check (CRC) code is derived from the further interleaved words, and this CRC code is added to the interleaved words, all of which are transmitted as a transmission block. An example of this technique is described in copending application Ser. No. 195,625, filed Oct. 9, 1980. However, by using a CRC code, the available "data slots" for useful information, that is, for the PCM words, is reduced. That is, in order to achieve improved error correction, it is necessary to transmit relatively "redundant" information, that is, it is necessary to transmit error-correction parity words and an error-detection CRC code, none of which represents useful information.
Techniques have been proposed whereby the CRC code need not be transmitted. Such techniques employ the so-called b-adjacent code, the BCH (Bose-Chaudhuri-Hocqueghem) code or the like as a parity word, such as described in U.S. Pat. No. 3,629,824 or in U.S. Pat. No. 3,697,948. In accordance with these techniques, any word in a block can be corrected without first identifying the particular word that is erroneous. However, this technique generally is limited to errors which occur only in a single block. Furthermore, the parity code generally exhibits a significant redundancy in each block; thereby further limiting the data slots which are available for useful information.
There is, therefore, a need to provide an error-correction encoding technique in which error-correction codes, or words, such as parity words, are not highly redundant and, moreover, the encoded information need not be accompanied by an error-detection code, such as the CRC code. There also is a need for such an error-correction encoding technique which is relatively simple to implement.